/**
 * 416. Partition Equal Subset Sum 分割等和子集
 * https://leetcode.com/problems/partition-equal-subset-sum/description/
 */
class PartitionEqualSubsetSum {
    /**
     * 方法： 使用动态规划判断数组是否可以分割成两个和相等的子集
     *       dp[j]表示是否可以从数组中选择若干个数使其和为j
     *       对于每个数x，从大到小更新dp[j]:
     *       dp[j] = dp[j] || dp[j-x]
     *       如果dp[s]为真，说明可以找到和为s的子集，则可以分割
     *
     * Args:
     *      nums: int[] - 输入的整数数组
     *
     * Returns:
     *      boolean: 数组是否可以分割成两个和相等的子集
     *
     * Time: O(n*s) - n为数组长度，s为数组和的一半
     *
     * Space: O(s) - 需要一个长度为s的数组存储动态规划状态
     */
    public boolean canPartition(int[] nums) {
        int s = 0;
        for(int x : nums){
            s += x;
        }
        if(s % 2 != 0){
            return false;
        }
        s = s/2;
        boolean[] dp = new boolean[s+1];
        dp[0] = true;
        int s2 = 0;
        for(int x : nums){
            s2 = Math.min(s2 + x, s);
            for(int j = s2; j >= x; j--){
                dp[j] = dp[j] || dp[j-x];
            }
            if(dp[s]){
                return true;
            }
        }
        return false;
    }
}